/*    
 * A* algorithm implementation.
 * Copyright (C) 2007, 2009 Giuseppe Scrivano <gscrivano@gnu.org>

 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
                       
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.

 * You should have received a copy of the GNU General Public License along
 * with this program; if not, see <http://www.gnu.org/licenses/>.
 */
package pathfinder;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class PathFinder extends AStar<PathFinder.Node>
{
				static int _xFin;
				static int _yFin;
                private int[][] map;

                static ArrayList<PathFinder.Node> posicoesGeradas;
                
                
                public static class Node{
                                public int x;
                                public int y;
                                public Node(int x, int y){
                                                this.x = x;
                                                this.y = y;
                                }
                                public String toString(){
                                                return "(" + x + ", " + y + ") ";
                                }

                }
                public PathFinder(int[][] map){
                                this.map = map;
                                posicoesGeradas = new ArrayList<PathFinder.Node>();
                }

                protected boolean isGoal(Node node){
                                return (node.x == _xFin) && (node.y == _yFin);
                }

                protected Double g(Node from, Node to){

                                if(from.x == to.x && from.y == to.y)
                                                return 0.0;

                                if(map[to.y][to.x] == 1)
                                                return 1.0;

                                return Double.MAX_VALUE;
                }

                protected Double h(Node from, Node to){
                                /* Use the Manhattan distance heuristic.  */
                                return new Double(Math.abs(map[0].length - 1 - to.x) + Math.abs(map.length - 1 - to.y));
                }

                public boolean contemIsto(ArrayList<PathFinder.Node> lista, PathFinder.Node n){
                	
                	for(int i=0; i < lista.size(); i++){
                		if(lista.get(i).x == n.x && lista.get(i).y == n.y)
                			return true;
                	}
                	
                	return false;
                }
                
                protected List<Node> generateSuccessors(Node node){
                                List<Node> ret = new LinkedList<Node>();
                                int x = node.x;
                                int y = node.y;
                                
                                if(y > 0 && map[y-1][x] == 1 && !contemIsto(posicoesGeradas,(new Node(x, y-1)))){
                                    ret.add(new Node(x, y-1));
                                    posicoesGeradas.add(new Node(x, y-1));
                                }

                                if(x > 0 && map[y][x-1] == 1 && !contemIsto(posicoesGeradas,(new Node(x-1, y)))){
                                    ret.add(new Node(x-1, y));
                                    posicoesGeradas.add(new Node(x-1, y));
                                }
                                
                                if(y < map.length - 1 && map[y+1][x] == 1 && !contemIsto(posicoesGeradas,(new Node(x, y+1)))){
                                                ret.add(new Node(x, y+1));
                                                posicoesGeradas.add(new Node(x, y+1));
                                }
                                
                                if(x < map[0].length - 1 && map[y][x+1] == 1 && !contemIsto(posicoesGeradas,(new Node(x+1, y)))){
                                                ret.add(new Node(x+1, y));
                                                posicoesGeradas.add(new Node(x+1, y));
                                }
                                
                                

                                return ret;
                }

                public static String calculatePath(int[][] map, int xIni, int yIni, int xFin, int yFin){
                               
                	
                	_xFin = xFin;
                	_yFin = yFin;
                
                				
                                PathFinder pf = new PathFinder(map);


                     
                                long begin = System.currentTimeMillis();

                                
                                
                                
                                
                                List<Node> nodes = pf.compute(new PathFinder.Node(xIni, yIni));
                               
                                long end = System.currentTimeMillis();


                                
                                if(nodes == null)
                                                return "noPath";
                                else if(nodes.size() == 1)
                                	return "atDoor";
                                else{
                                	int pos1X = nodes.get(0).x;
                                	int pos1Y = nodes.get(0).y;
                                	int pos2X = nodes.get(1).x;
                                	int pos2Y = nodes.get(1).y;
                                	
                                	if(pos1X == pos2X){
                                		int direction = pos1Y - pos2Y;
                                		if(direction > 0)
                                			return "S";
                                		else return "N";
                                	} else{
                                		int direction = pos1X - pos2X;
                                		if(direction > 0)
                                			return "W";
                                		else return "E";
                                	}
                                	
                                	
                                }
                }

}

